Перейти к основному содержимому

3.02. История развития структур данных

В РАЗРАБОТКЕНЕ ДЛЯ НОВИЧКОВНЕ ОБЯЗАТЕЛЬНО
Разработчику Архитектору Инженеру

Внимание
Приготовьтесь! Страшные слова Структуры, типы данных – это очень важно. Это фундаментальные знания, которые помогут вам изучать всё в дальнейшем быстрее и эффективнее. Некоторые вещи будут пока не понятны, главное пробегитесь, и возвращайтесь к разделу в дальнейшем, если понадобится.

История развития структур данных​

Структура данных — это способ организации, хранения и доступа к информации в памяти вычислительной системы с целью обеспечения эффективного выполнения операций над этой информацией. Алгоритм определяет что и как делается, а структура данных — где и в какой форме хранятся данные, необходимые для выполнения этих действий. Эффективность многих алгоритмов напрямую зависит от выбора структуры данных: например, поиск элемента в неупорядоченном списке требует последовательного перебора, тогда как в сбалансированном дереве поиска он может быть выполнен за логарифмическое время относительно количества элементов.

Структуры данных возникли как практические ответы на конкретные инженерные и вычислительные задачи. На ранних этапах развития вычислительной техники объём оперативной памяти измерялся в байтах и словах, процессоры работали на тактовых частотах в килогерцах, а программы вручную управляли каждым битом. В этих условиях оптимизация использования памяти и времени выполнения была не просто желательной — она была необходимой для выполнимости задач вообще. Именно в таких условиях и сформировались первые концепции, которые позже легли в основу современных структур данных.

Историю развития структур данных условно можно разделить на несколько этапов, соответствующих технологическим и концептуальным вехам в эволюции программирования и вычислительных систем:

  1. Докомпьютерный и ранний компьютерный период (до 1950‑х) — появление примитивных форм организации данных в механических и электромеханических устройствах, а затем в первых программируемых машинах.
  2. Формирование основ (1950‑е — начало 1960‑х) — появление первых языков высокого уровня (Фортран, АЛГОЛ) и сопутствующих им идей динамического выделения памяти, указателей и рекурсивных структур.
  3. Период систематизации и математизации (середина 1960‑х — начало 1970‑х) — появление фундаментальных работ Дональда Кнута, Никлауса Вирта, Тони Хоара и других, в которых структуры данных рассматриваются как объект теоретического анализа.
  4. Эра абстрактных типов данных и модульности (1970‑е — 1980‑е) — развитие концепции инкапсуляции, появление объектно-ориентированных языков, формализация интерфейсов структур данных.
  5. Параллелизм, распределённость и внешняя память (1990‑е — 2000‑е) — адаптация классических структур к многопоточным и многопроцессорным системам, к ограничениям внешней памяти (дисковая подсистема), к потребностям баз данных и веб-масштабных приложений.
  6. Современные тенденции (2010‑е — настоящее время) — появление структур, ориентированных на кэш-эффективность, функциональную неизменяемость, строгую типизацию, а также специализированные структуры для работы с потоками данных, графами, пространственными и временными рядами.

Рассмотрим каждый из этих этапов подробно.

1. Докомпьютерный и ранний компьютерный период (до 1950‑х)​

Понятие структуры данных в современном виде предполагает программную реализацию, однако его корни уходят в практику ручной обработки информации. Например, в библиотечных каталогах карточки размещались в алфавитном порядке — это ранняя форма упорядоченного массива с лексикографическим ключом. В делопроизводстве использовались журналы, реестры, инвентарные описи — все они содержали элементы с фиксированным набором полей (номер, дата, описание), то есть представляли собой структуры с предопределённой схемой, аналогичные записям или объектам.

Первые электромеханические вычислительные машины, такие как IBM 405 (1930‑е) или Harvard Mark I (1944), работали с данными, представленными в виде перфокарт или бумажных лент. Каждая карта или участок ленты содержал фиксированное количество полей, и порядок их расположения задавался физически (например, колонками на карте). Это можно рассматривать как прототип примитивного одномерного массива с жёстко заданной длиной и типом элементов — каждое поле было либо числовым, либо алфавитным, и его позиция в карте определяла семантику.

Ключевым ограничением того времени была невозможность динамического изменения формы хранения в процессе вычислений: структура данных была «зашита» в аппаратуру или в физический носитель. Программист (ещё не существовавшая профессия) должен был заранее продумать, сколько записей будет обрабатываться, какого размера поля им нужны, в каком порядке будут производиться операции.

С появлением первых программируемых электронных машин — ENIAC (1945), EDVAC (1949), EDSAC (1949), — возникла возможность изменять способ адресации памяти. Архитектура фон Неймана, предложенная в 1945 году, ввела принцип хранения программы и данных в едином адресном пространстве. Это позволило программам работать не только с предопределёнными константами, но и с переменными, значения которых менялись в ходе выполнения. Появилась возможность организовывать данные не только как набор независимых ячеек, но и как логически связанные группы.

В этих машинах память состояла из ртутных линий задержки, магнитных барабанов или электростатических трубок — устройств с последовательным доступом или с высокой латентностью. Операция чтения ячейки с произвольным адресом могла занимать десятки тактов. Поэтому первые «структуры данных» были по сути линейными последовательностями: массивы реализовывались как фиксированные блоки памяти, к которым обращались по смещению от базового адреса. Такой подход позволял вычислять физический адрес нужного элемента всего за несколько арифметических операций, что было критически важно при медленной памяти.

Существовало понятие таблицы — заранее выделенного участка памяти, предназначенного для хранения однотипных записей. Таблица могла использоваться для имитации функций (табличные вычисления), для хранения констант (например, таблицы тригонометрических функций) или для временного размещения промежуточных результатов. Уже здесь проявилась идея индексации: если известно, что i-й элемент таблицы находится на расстоянии i × w байт от начала, где w — размер элемента, то к нему можно получить доступ без перебора всех предыдущих. Формулу мы опускаем, но принцип линейного смещения был заложен в ассемблерные инструкции того времени.

Важно отметить, что на этом этапе не существовало понятия типа данных в современном смысле. Программист вручную интерпретировал битовые шаблоны как числа, символы или адреса. Разделение на целые, дробные и символьные данные появилось позже, вместе с развитием языков высокого уровня.

Таким образом, на раннем этапе возникли два фундаментальных принципа, которые сохраняются до сих пор:

  • Линейная адресация — представление сложной структуры как непрерывного или сегментированного блока с вычислимым смещением;
  • Жёсткая схема — фиксированный формат записи, задаваемый заранее и не допускающий вариативности.

Эти принципы легли в основу массивов и записей — первых структур данных, получивших теоретическое обоснование и практическое применение.

2. Формирование основ: динамические структуры и указатель как универсальный инструмент (1950‑е — начало 1960‑х)​

К середине 1950‑х годов стало ясно, что линейные массивы и фиксированные таблицы недостаточны для решения задач символической обработки, в частности — в области машинного перевода, лингвистики, алгебраических вычислений и логического вывода. Эти задачи требовали работы с данными переменной длины, вложенными конструкциями и произвольными связями между элементами. Например, при анализе грамматики предложения необходимо было представлять дерево разбора, где количество дочерних узлов у каждого родителя непредсказуемо и зависит от конкретного текста. Массивы фиксированной размерности не могли эффективно выразить такую гибкость.

Переломный момент наступил с появлением языка ЛИСП (LISt Processor), разработанного Джоном Маккарти и его коллегами в Массачусетском технологическом институте в 1958 году. Хотя первоначально ЛИСП задумывался как инструмент для реализации теории рекурсивных функций, он стал первой практической системой, в которой структура данных являлась одновременно и программой. В основе ЛИСПа лежала концепция связанного списка, реализованного через пары (cons-ячейки), каждая из которых содержала два поля: car (содержимое) и cdr (ссылка на следующую ячейку). Такая ячейка — минимальная единица данных — позволяла строить линейные списки, деревья, графы и произвольные вложенные структуры.

Ключевым инновационным элементом здесь был указатель (в терминологии того времени — ссылка, адрес ячейки, link). В отличие от индекса в массиве, который предполагает линейное пространство и вычислимое смещение, указатель представлял собой значение, хранящееся в ячейке и интерпретируемое как адрес другой ячейки в памяти. Благодаря указателям связи между элементами могли быть установлены и изменены динамически, в процессе выполнения программы, без необходимости перемещать или копировать большие объёмы данных. Это позволяло реализовывать операции вставки и удаления за фиксированное время при условии наличия ссылки на узел-предшественник — свойство, недостижимое для плотных массивов без сдвига содержимого.

Важно подчеркнуть, что указатель в ЛИСПе не был привязан к конкретному типу данных: одна и та же cons-ячейка могла ссылаться на число, на другую пару, на символ или даже на функцию. Так сформировалась идея однородного представления данных, в которой различие между структурами вводилось на уровне интерпретации — то есть через поведение программ, работающих с ними. Это стало предпосылкой для позднейшей концепции абстрактных типов данных.

Практическая реализация списков в ЛИСПе потребовала решения двух фундаментальных инженерных проблем:

  1. Управление динамической памятью — поскольку объекты создавались и уничтожались в ходе вычислений, необходимо было отслеживать, какие ячейки свободны, а какие заняты. Для этого в 1960 году был предложен алгоритм сборки мусора по принципу пометки и сбора (mark-and-sweep), также разработанный в группе Маккарти. Этот алгоритм позволял автоматически освобождать память, недостижимую из текущего состояния программы, и стал первым системным механизмом, встроенным в среду выполнения для поддержки динамических структур. Его появление означало переход от ручного управления ресурсами к автоматическому — революционный сдвиг в архитектуре программного обеспечения.
  2. Работа со свободной памятью как со списком — свободные ячейки сами организовывались в связанный список, из которого при запросе памяти (например, при выполнении cons) извлекалась первая доступная ячейка. Таким образом, даже механизм управления памятью использовал ту же структуру данных, что и пользовательские программы, демонстрируя рефлексивность: структура данных применяется для описания самой себя.

Параллельно с развитием ЛИСПа в других научных центрах формировались альтернативные подходы. В Кембриджском университете Тони Хоар, работая над задачами обработки символьных выражений, ввёл понятие стека как самостоятельной структуры данных. Стек (от англ. stack — стопка) реализует принцип «последним пришёл — первым ушёл» (LIFO, last-in, first-out) и оказался исключительно удобным для:

  • хранения контекста вызовов подпрограмм (возвратный адрес, локальные переменные);
  • вычисления выражений в постфиксной (обратной польской) записи;
  • реализации рекурсивных алгоритмов без явного использования рекурсии в коде.

Хоар показал, что стек может быть эффективно реализован как массив с переменной вершиной (указатель top), что делает все операции — добавление, удаление, чтение вершины — константными по времени и не требующими динамического выделения памяти на каждом шаге. Это сделало стек одной из самых «дешёвых» и надёжных структур, и к началу 1960‑х годов он был аппаратно поддержан во многих архитектурах (например, в IBM 7090 и Atlas).

Также в это время получила распространение структура очередь (FIFO, first-in, first-out), применяемая для моделирования процессов, где требуется соблюдение порядка поступления: буферизация ввода‑вывода, планирование задач, обработка событий. Простейшая реализация очереди — на основе кольцевого буфера (циклического массива) с двумя указателями (head и tail) — обеспечивала эффективное использование памяти и константное время операций при условии фиксированной ёмкости. Для динамических очередей использовались связанные списки, хотя с потерей локальности обращений.

Важным теоретическим и педагогическим вкладом стал язык АЛГОЛ 60, представленный в 1960 году. Хотя АЛГОЛ сам по себе не вводил новых структур данных напрямую, его отчёт («Алгоритмический язык АЛГОЛ 60») впервые чётко разделил:

  • синтаксис — правила построения корректных программ;
  • семантику — смысл операторов и выражений;
  • процедурную абстракцию — возможность выделения подпрограмм с локальными переменными и рекурсией.

Благодаря рекурсии стало возможным естественное описание алгоритмов, оперирующих с древовидными структурами: обход дерева, сортировка слиянием, быстрая сортировка. Рекурсия и динамические структуры оказались взаимно усиливающими друг друга: без списков и деревьев рекурсия была бы ограничена простыми числовыми вычислениями; без рекурсии — обработка вложенных структур требовала бы явного управления стеком вручную.

К началу 1960‑х годов сложился набор базовых структур, которые можно считать «атомарными» строительными блоками:

  • Массив — линейная последовательность с произвольным доступом по индексу;
  • Связанный список — последовательность узлов, связанных указателями;
  • Стек — структура с дисциплиной доступа LIFO, часто реализуемая массивом или списком;
  • Очередь — структура с дисциплиной доступа FIFO;
  • Запись (структура) — композитный тип с именованными полями фиксированного состава (реализовывалась в Фортране как COMMON‑блоки или в ранних версиях Кобола как 01‑уровневые группы).

Эти структуры уже позволяли решать подавляющее большинство практических задач того времени — от научных расчётов до бухгалтерского учёта. Однако их применение оставалось преимущественно императивным и неформализованным: программисты использовали их на основе интуиции и опыта, без строгого анализа сложности, инвариантов или доказательств корректности.

3. Систематизация и математизация (середина 1960‑х — начало 1970‑х)​

К середине 1960‑х годов накопилось достаточное количество опыта в использовании базовых структур данных, чтобы возникла потребность в их классификации, сравнении и обосновании. Программы становились сложнее, ошибки в управлении памятью и логике доступа к данным — дороже, а требования к производительности — строже. В этих условиях появилась необходимость в теории структур данных: «почему это работает», «насколько быстро», «в каких условиях применимо» и «как доказать, что оно корректно».

Главная заслуга в создании такой теории принадлежит Дональду Кнуту. Его многотомный труд «Искусство программирования» (первый том вышел в 1968 году) стал фундаментальным трудом, в котором структуры данных и алгоритмы рассматриваются как две стороны одной медали, анализируемые с позиций дискретной математики, теории вероятностей и асимптотического анализа. Кнут ввёл в обиход программистского сообщества такие понятия, как:

  • временная и пространственная сложность (в терминах O, Ω, Θ);
  • амортизированная стоимость операции (например, при расширении динамического массива);
  • инварианты структуры — условия, сохраняющиеся на всём протяжении жизненного цикла структуры и гарантирующие её корректное функционирование.

В первом томе Кнут подробно рассматривает такие структуры, как стеки, очереди, списки, деревья и хеш-таблицы, причём математическое моделирование их поведения. Например, он анализирует ожидаемую глубину поиска в случайном бинарном дереве, показывает, как свойства входных данных влияют на производительность хеширования, выводит формулы для числа сравнений в различных схемах сортировки — всё это без привязки к конкретному языку или архитектуре.

Особое внимание Кнут уделил деревьям, которые в его изложении получили статус центральной структуры для представления иерархических отношений. Он систематизировал семейство деревьев:

  • бинарные деревья — каждый узел имеет не более двух потомков;
  • упорядоченные деревья — фиксированный порядок следования потомков;
  • деревья поиска — для каждого узла все ключи в левом поддереве меньше, а в правом — больше;
  • сбалансированные деревья — в частности, AVL‑деревья (названы по именам Адельсона-Вельского и Ландиса, 1962), в которых разность высот поддеревьев ограничена единицей, что гарантирует логарифмическую глубину и, следовательно, логарифмическое время поиска, вставки и удаления.

Важно отметить: AVL‑деревья были предложены до выхода книги Кнута, но именно он впервые дал исчерпывающее описание их свойств, алгоритмов балансировки (включая случаи одинарного и двойного вращения) и доказал их корректность. Это стало образцом того, как практическая инженерная конструкция может быть подвергнута строгому математическому анализу.

Почти одновременно с Кнутом Никлаус Вирт в Цюрихском университете разрабатывал язык Паскаль (первый компилятор — 1970). Хотя Паскаль часто воспринимается как учебный язык, его значение в истории структур данных трудно переоценить. Вирт ввёл в Паскаль:

  • записи (record) как составные типы с именованными полями — формализацию того, что ранее реализовывалось через смещения в памяти;
  • доступ по указателю (^) с синтаксической поддержкой (new, dispose);
  • строгое разделение между статическими и динамическими данными: статические переменные размещались в фиксированном сегменте памяти, динамические — в «куче» (heap), управляемой программистом.

Более того, Вирт в своей книге «Алгоритмы + структуры данных = программы» (1975, подготовленной на основе лекций 1971–1973 гг.) сформулировал ключевой тезис, давший название главе: эффективность программы определяется адекватностью выбранной структуры данных. Он показал, как одна и та же задача — например, сортировка — может быть решена радикально по-разному в зависимости от того, хранятся ли данные в массиве, в списке или в дереве. Паскаль стал первым широко распространённым языком, в котором структуры данных были не побочным эффектом реализации, а явной, декларативной частью языка.

Параллельно Эдсгер Дейкстра и Тони Хоар развивали формальные методы верификации программ. Хоар ввёл в 1969 году логику Хоара — систему аксиом и правил вывода для доказательства частичной и полной корректности программ. В рамках этой логики структуры данных описываются через предусловия и постусловия операций: например, постусловие операции push для стека утверждает, что верхний элемент стека равен вставленному значению, а остальное содержимое сохранено. Это позволило рассматривать структуры данных как абстрактные машины, поведение которых определяется интерфейсом, а не реализацией.

Ключевым следствием этого подхода стало появление концепции абстрактного типа данных (АТД). Хотя термин ещё не был устоявшимся, идея уже зрела: структура данных определяется набором операций и их семантическими свойствами (инвариантами, пред- и постусловиями). Например, очередь характеризуется тем, что элемент, добавленный первым, будет удалён первым — независимо от того, реализована она на массиве, списке или буфере с переносом. Это позволило разделять спецификацию и реализацию, что стало основой для модульного программирования.

Также в этот период произошли важные инженерные достижения:

  • Хеш-таблицы получили теоретическое обоснование. Хотя идея хеширования восходит к работам Ханса Петерсона (1955) и Герберта Думея (1956), именно в 1968 году Вирт и Кнут независимо предложили методы разрешения коллизий — линейное пробирование и цепочки — и проанализировали их поведение в среднем и в худшем случае.
  • Бинарные кучи были формализованы Дж. Уильямсом в 1964 году как эффективная структура для реализации очереди с приоритетами. Кнут включил их в анализ алгоритма пирамидальной сортировки (heapsort), показав, что на основе одной и той же структуры можно строить как алгоритмы сортировки, так и динамические приоритетные очереди.

К началу 1970‑х годов сложился устойчивый канон фундаментальных структур данных, который практически без изменений преподаётся в университетах до сих пор:

  • линейные: массивы, списки, стеки, очереди;
  • древовидные: бинарные деревья, деревья поиска, сбалансированные деревья (AVL);
  • хеш-структуры: хеш-таблицы с цепочками и открытой адресацией;
  • приоритетные: бинарные кучи.

Эти структуры были классифицированы, проанализированы, доказаны и описаны в независимой от платформы форме. Программист получил не набор трюков, а теоретический инструментарий для обоснованного выбора.

4. Эра абстрактных типов данных и модульности (1970‑е — 1980‑е)​

Если 1960‑е годы дали математическую основу структур данных, то 1970‑е — инженерную методологию их применения в крупномасштабных проектах. Рост сложности программного обеспечения (операционные системы, СУБД, компиляторы) сделал невозможным централизованное управление структурами: одна и та же очередь или дерево могли использоваться в разных модулях, разрабатываемых независимыми командами. Возникла острая потребность в механизмах, позволяющих:

  • скрыть детали реализации структуры от её пользователей;
  • гарантировать, что изменения в реализации не нарушат работу зависящих компонентов;
  • определять поведение структуры через формальный интерфейс — набор операций с чёткими контрактами.

Эту потребность удовлетворила концепция абстрактного типа данных (АТД), получившая своё название и формальное определение в начале 1970‑х. Термин впервые был предложен в работах Барбары Лисков и её коллег в Массачусетском технологическом институте, особенно в контексте языка CLU (от CLUster), созданного в 1974 году. CLU стал первым языком, в котором АТД были встроены на уровне синтаксиса.

В CLU абстрактный тип определялся как кластер — модуль, объединяющий:

  • набор операций (функций и процедур), доступных извне (интерфейс);
  • внутреннее представление данных (реализация), недоступное напрямую для внешнего кода;
  • инварианты, поддерживаемые операциями кластера.

Например, очередь в CLU определялась как объект, поддерживающий операции create, enqueue, dequeue, empty, причём реализация могла использовать массив, связанный список или любую другую внутреннюю структуру — при условии соблюдения семантики FIFO. Это позволяло менять реализацию (например, перейти от линейного списка к циклическому буферу для повышения локальности кэша) без изменения кода, использующего очередь.

Важной особенностью CLU была поддержка исключений и проверки инвариантов на этапе выполнения. Каждая операция кластера могла включать проверку предусловий (например, dequeue требует, чтобы очередь не была пуста), что делало АТД не просто удобной абстракцией, но и инструментом повышения надёжности.

Почти одновременно в Швейцарии Никлаус Вирт разрабатывал язык Modula‑2 (1978), который внёс в практику модульного программирования понятия модуля и отделения интерфейса от реализации на уровне компиляции. В Modula‑2 каждый модуль состоял из двух файлов:

  • определения (.DEF) — содержал объявления типов, констант, процедур, доступных другим модулям;
  • реализации (.IMP) — содержал тело процедур и внутренние данные.

Таким образом, структуры данных, определённые в модуле, могли быть экспортированы как непрозрачные типы: пользователь знал их имя и доступные операции, но не мог напрямую обращаться к полям или манипулировать указателями внутри. Это стало промышленным стандартом инкапсуляции задолго до появления объектно-ориентированных языков.

Существенно, что в 1970‑е годы не существовало единого «правильного» способа реализации даже базовых АТД. Например, для очереди с приоритетами возникло несколько конкурирующих подходов:

  • бинарная куча — простая в реализации, эффективна по памяти, но не поддерживает эффективное уменьшение ключа (decrease-key), что критично для алгоритмов вроде Дейкстры;
  • левосторонние кучи (leftist heaps, Кнут и др., 1970‑е) — позволяли сливать кучи за логарифмическое время;
  • биномиальные кучи (Jean Vuillemin, 1978) — обеспечивали эффективное объединение (merge), что важно в функциональных языках;
  • фибоначчиевы кучи (Michael Fredman и Robert Tarjan, 1984, но подготовительные работы начались в конце 1970‑х) — вводили концепцию отложенной балансировки, чтобы сделать операции insert и decrease-key амортизированно константными.

Это разнообразие демонстрирует, что к 1980‑м годам выбор структуры данных стал проектировочным решением, определяемым конкретными требованиями к операциям, частоте вызовов, допустимой сложности реализации и особенностям среды исполнения.

Параллельно развивалась объектно-ориентированная парадигма, которая органично впитала идею АТД. Язык Симула‑67 (Оле-Йохан Даль и Кристен Нюгорд, 1967) ввёл понятия класса и объекта — первые инструменты для моделирования структур данных как сущностей с внутренним состоянием и поведением. Однако массовое внедрение произошло позже, с появлением Smalltalk‑80 (Алан Кэй и др.). В Smalltalk все структуры данных — массивы, словари, множества — были реализованы как классы, наследующие от общего предка Object. Поведение определялось методами, переопределяемыми в подклассах; инкапсуляция обеспечивалась тем, что доступ к полям объекта был возможен только через методы.

Smalltalk продемонстрировал мощь унификации: например, метод at: (чтение по индексу) можно было вызвать и для массива, и для строки (если рассматривать её как массив символов), и для пользовательской структуры, реализующей тот же протокол. Это стало предпосылкой к появлению интерфейсов и протоколов в последующих языках.

В 1980‑е годы ключевую роль сыграл язык C++, разработанный Бьёрном Страуструпом. Первоначально задуманный как «C с классами» (1980), к середине десятилетия он эволюционировал в полноценную систему поддержки АТД с помощью:

  • классов — объединяющих данные и методы;
  • перегрузки операторов — позволявшей использовать привычный синтаксис ([], +, <<) для пользовательских типов;
  • механизмов управления ресурсами — в частности, деструкторов, которые обеспечивали автоматическое освобождение памяти при выходе из области видимости (RAII — Resource Acquisition Is Initialization).

Библиотека классов, поставляемая с ранними версиями C++ (впоследствии ставшая основой для STL), уже содержала шаблонные реализации vector, list, stack, queue, map, set — все они были АТД, реализованные с учётом эффективности и безопасности. Особенно важно, что использование шаблонов (введённых в C++ в 1987–1988 гг.) позволило отделить логику структуры от типа хранимых элементов, что сделало код многократно переиспользуемым без потери производительности (в отличие от универсальных указателей void* в C).

В это же время в академической среде получила развитие теория алгебраических спецификаций (например, метод Larch в MIT, 1980‑е), в которой АТД описывались как множества уравнений, связывающих операции: например, dequeue(enqueue(Q, x)) = Q, если Q не пуст. Это позволяло формально верифицировать реализации на соответствие спецификации.

Таким образом, к концу 1980‑х годов сложилась устойчивая инженерная практика:

  • структура данных проектируется как АТД с чётко определённым интерфейсом;
  • реализация скрыта и может быть заменена без влияния на клиентский код;
  • выбор конкретной реализации (например, хеш-таблица против сбалансированного дерева для словаря) обосновывается требованиями к производительности, памяти и семантике;
  • стандартные библиотеки предоставляют готовые, протестированные реализации базовых АТД.

Этот подход позволил масштабировать разработку: команды могли параллельно работать над разными модулями, полагаясь на контракты, а не на детали реализации. Структуры данных перестали быть «внутренней кухней» программы и стали строительными блоками архитектуры.

5. Параллелизм, распределённость и внешняя память (1990‑е — 2000‑е)​

С окончанием эпохи быстрого роста тактовых частот процессоров (закон Мура в части частоты замедлился после ~2005 года) и массовым внедрением многоядерных архитектур (Intel Core 2 Duo — 2006, AMD Opteron — с поддержкой NUMA с 2003 года) производительность программ всё чаще стала определяться не количеством выполненных операций, а характером доступа к данным. В этом контексте классические структуры данных потребовали пересмотра по трём ключевым направлениям:

5.1. Конкурентные и параллельные структуры данных​

В однопоточных программах корректность структуры данных обеспечивалась последовательным выполнением операций: если инвариант соблюдён до вызова insert, и сама операция реализована правильно, то инвариант сохраняется после неё. В многопоточной среде две операции могут выполняться одновременно или перемежаться на уровне отдельных инструкций, что приводит к гонкам данных, повреждению структуры и неопределённому поведению.

Первые подходы к решению этой проблемы были прямыми: блокировки (mutex, semaphore). Например, каждый метод очереди (или дерева, или хеш-таблицы) окружался захватом общего мьютекса. Такой подход гарантировал корректность, но уничтожал параллелизм: даже независимые операции (например, чтение из разных частей хеш-таблицы) вынуждены были ждать друг друга. Такие структуры называли грубо блокированными (coarse-grained locking).

Более тонкие стратегии появились в 1990‑е и получили развитие в 2000‑е:

  • Тонкое блокирование (fine-grained locking) — каждый узел дерева или сегмент хеш-таблицы защищался собственным мьютексом. Например, в сбалансированном дереве при вставке блокировались только узлы на пути от корня к листу, что позволяло параллельно модифицировать непересекающиеся поддеревья.
  • Блокирование на основе чтения-записи (readers-writer locks) — позволяло нескольким потокам-читателям одновременно обращаться к структуре, в то время как записывающий поток получал исключительный доступ. Полезно для структур с преобладанием операций чтения (например, кэши).
  • Блокирование без ожидания (non-blocking algorithms) — наиболее продвинутый класс, основанный на атомарных операциях процессора: сравнить-и-обмен (compare-and-swap, CAS), загрузить-связано/сохранить-условно (LL/SC). Алгоритмы этого класса гарантируют, что хотя бы один поток прогрессирует, даже если другие зависли или завершились аварийно.

Первые неблокирующие структуры появились в академических работах 1990‑х. Например:

  • неблокирующий стек Майкла‑Скотта (1996) — реализация стека на основе связанного списка с CAS‑операцией при вставке и удалении. Каждая операция пытается атомарно обновить указатель на вершину; при конфликте она повторяется, но никогда не блокируется.
  • неблокирующая очередь Майкла‑Скотта (та же работа) — двухсвязный список с отдельными указателями на голову и хвост, также управляемый CAS.

Ключевое преимущество неблокирующих структур — отсутствие взаимной блокировки (deadlock), голодания (starvation) и зависимости от планировщика ОС. Они особенно важны в системах реального времени и в ядре операционных систем.

Однако их реализация крайне сложна: необходимо учитывать логику структуры и тонкости модели памяти процессора (порядок видимости изменений, барьеры памяти), а также обеспечивать корректную сборку мусора (в языках со сборщиком) или безопасное удаление узлов (вручную, через опасную задержку — hazard pointers, или эпохальную отложенную деаллокацию — epoch-based reclamation).

К середине 2000-х неблокирующие структуры начали входить в стандартные библиотеки: Java 5 (2004) представила пакет java.util.concurrent с ConcurrentHashMap, ConcurrentLinkedQueue, CopyOnWriteArrayList; в C++11 (2011) появилась поддержка атомарных операций и барьеров памяти, что позволило писать такие структуры и на C++.

5.2. Структуры данных для внешней памяти (дисковых систем)​

Пока оперативная память росла, многие приложения могли держать данные целиком в RAM. Однако с ростом объёмов данных (веб-индексы, транзакции, логи) стало ясно, что хранение на диске неизбежно. А время доступа к диску (десятки миллисекунд для HDD) превышает время доступа к памяти (наносекунды) на шесть порядков. Это означало, что оптимизация количества операций ввода-вывода (I/O) важнее оптимизации числа сравнений или сдвигов.

Классические структуры, такие как бинарное дерево поиска, оказываются неэффективными на диске: каждый узел лежит в отдельном блоке, и поиск элемента требует чтения O(log₂ N) блоков — но если логарифм берётся по основанию 2, а размер блока — 4 КБ, то для 1 млн записей потребуется ~20 чтений. Это недопустимо.

Решение пришло из теории баз данных: B‑деревья и их варианты (B⁺‑деревья, B*‑деревья), впервые описанные Рудольфом Бэром в 1972 году, но получившие широкое применение именно в 1990‑е — 2000‑е с развитием СУБД и файловых систем.

Идея B‑дерева — максимизировать ветвление (branching factor): каждый узел содержит не два, а m ключей и m+1 указателей на потомков, где m подбирается так, чтобы узел занимал примерно один дисковый блок. При m = 100 глубина дерева для миллиарда записей — всего 3–4 уровня, то есть поиск требует 3–4 операций чтения. При этом вставка и удаление сопровождаются разделением и слиянием узлов, что сохраняет сбалансированность без частых перестроек.

B⁺‑деревья, ставшие стандартом для индексов в реляционных СУБД (Oracle, PostgreSQL, MySQL/InnoDB), дополнительно улучшают локальность последовательного доступа: листовые узлы связаны в двусвязный список, что позволяет эффективно выполнять диапазонные запросы (WHERE key BETWEEN a AND b).

В это же время появились специализированные структуры для потоковой и append-only записи:

  • LSM‑деревья (Log-Structured Merge-Trees, Patrick O’Neil et al., 1996) — используются в системах вроде LevelDB, RocksDB, Cassandra. Новые данные сначала пишутся последовательно в мемтаблицу (в памяти), затем сбрасываются на диск как неизменяемые файлы (SSTables), которые периодически сливаются (merge) в фоне. Такой подход превращает случайные записи в последовательные, что критично для SSD и HDD, но усложняет чтение (требуется проверка нескольких уровней).
  • Fractal Trees (TokuDB) — модификация B‑деревьев с буферами на каждом узле, позволяющими накапливать изменения и сливать их порциями, что снижает количество I/O-операций при интенсивной записи.

5.3. Распределённые структуры данных​

С развитием распределённых систем (кластеры, облачные платформы) возникла задача: как хранить и обрабатывать структуру данных, физически разбросанную по множеству узлов, с возможными задержками, сбоями и разделениями сети (partition tolerance)?

Ответы на неё легли в основу современных распределённых хранилищ:

  • Хеширование с согласованным кольцом (consistent hashing) — позволяет добавлять и удалять узлы с минимальной перебалансировкой данных (активно используется в Dynamo, Cassandra, Riak).
  • CRDT (Conflict-Free Replicated Data Types) — семейство структур, допускающих репликацию без централизованной синхронизации. Например, набор с добавлением (G-Set), счётчик с увеличением (PN-Counter), регистр с последней записью (LWW-Register). Их корректность обеспечивается коммутативностью, ассоциативностью и идемпотентностью операций — свойствами, гарантирующими сходимость при любом порядке доставки обновлений.

Таким образом, 1990‑е — 2000‑е годы перевели фокус с алгоритмической сложности на системные характеристики: латентность, пропускная способность, отказоустойчивость, масштабируемость. Структуры данных стали компонентами распределённой инфраструктуры.

6. Современные тенденции (2010‑е — настоящее время)​

Если 2000‑е годы были временем адаптации классических идей к параллелизму и распределённости, то 2010‑е — временем рефинемента, специализации и формализации. Структуры данных перестали быть универсальными «ящиками для данных» и превратились в тонко настраиваемые инструменты, оптимизированные под конкретные аппаратные особенности, модели программирования и доменные задачи.

6.1. Кэш-эффективность и иерархия памяти​

С середины 2000‑х годов разрыв между скоростью процессора и скоростью памяти продолжал расти. Современные CPU выполняют сотни операций за время, необходимое для загрузки одной линии кэша (64 байта) из оперативной памяти. В этих условиях число обращений к памяти и локальность данных стали доминирующими факторами производительности — даже более важными, чем асимптотическая сложность.

Это привело к возрождению интереса к плотным (dense), кэш-дружественным структурам, в первую очередь — к динамическим массивам и их расширениям. Хотя связанные списки привлекательны гибкостью, их узлы, разбросанные по памяти, вызывают промахи кэша (cache misses) при последовательном обходе. В ответ появились:

  • Вектора с резервированием (vector with reservation) — стандартная практика: выделять память с запасом, чтобы избежать частых реаллокаций и копирования.
  • Амортизированные массивы с экспоненциальным ростом — гарантируют, что средняя стоимость вставки остаётся константной без чрезмерного расхода памяти.
  • Пулы памяти и arena-аллокаторы — выделяют крупные блоки, из которых уже раздаются мелкие объекты. Это ускоряет аллокацию и повышает пространственную локальность: объекты, созданные в одном контексте, физически расположены близко.

Особое внимание уделяется структуре хранения записей:

  • Array of Structs (AoS) — классический подход: каждый элемент — структура из полей, массив — последовательность таких структур. Удобен для доступа к полному объекту, но неэффективен при обработке одного поля у множества элементов (например, в векторных вычислениях).
  • Struct of Arrays (SoA) — поля разнесены по отдельным массивам: [x1, x2, …, xn], [y1, y2, …, yn], [z1, z2, …, zn]. Позволяет загружать в кэш и SIMD‑регистры только нужные данные, минимизируя объём пересылок. Широко используется в игровых движках, научных вычислениях и системах обработки сигналов.

Другой важный класс — B‑деревья на основе кэш-линий. Исследования (например, работы MIT CSAIL, 2010‑е) показали, что оптимальное ветвление B‑дерева должно подбираться под размер кэш-линии процессора (обычно 64 байта). Такие деревья, иногда называемые Bε‑деревьями или cache-oblivious деревьями, минимизируют количество промахов кэша даже без знания параметров иерархии памяти.

6.2. Неизменяемость и функциональные структуры данных​

Рост популярности функционального программирования (Haskell, Scala, F#, Clojure, а также функциональные черты в JavaScript, Python, C#) потребовал пересмотра подхода к изменению состояния. В чисто функциональных языках структуры данных по умолчанию неизменяемы (immutable): любая «модификация» создаёт новую версию, оставляя исходную нетронутой.

На первый взгляд это ведёт к катастрофическому расходу памяти и времени. Однако благодаря структурному совместному использованию (structural sharing) можно достигать эффективности, близкой к изменяемым аналогам. Ключевые примеры:

  • Неизменяемый связанный список — при добавлении в голову (cons) создаётся только один новый узел, ссылающийся на старый список. Общая часть остаётся общей.
  • Неизменяемое сбалансированное дерево (например, красно-чёрное или AVL) — при вставке/удалении перестраиваются только узлы на пути от корня к изменённому листу (O(log N) новых узлов), остальное дерево разделяется.
  • Хеш‑массивные отображённые триэ (HAMT) — структура, лежащая в основе Map и Set в Clojure и Scala. Использует битовое хеширование ключей и 32‑арное (или 64‑арное) дерево, где каждый уровень соответствует фрагменту хеша. Обновление затрагивает только O(log₃₂ N) узлов, а чтение — без блокировок.
  • RRB‑деревья (Relaxed Radix Balanced Trees) — расширение HAMT, поддерживающее эффективную конкатенацию и нарезку (slice), что делает их пригодными для реализации неизменяемых векторов.

Преимущества неизменяемых структур:

  • потокобезопасность по умолчанию — разделяемые данные не требуют синхронизации;
  • отладка и тестирование — состояние не «утекает» и не меняется неожиданно;
  • откат и история — сохранение старых версий бесплатно (например, для реализации undo/redo или MVCC в СУБД).

Даже в императивных языках неизменяемость находит применение: в .NET и Java появились immutable collections (ImmutableList, ImmutableMap), которые строятся поверх изменяемых, но предоставляют безопасный интерфейс для многопоточной среды.

6.3. Типобезопасность и выразительность в статически типизированных языках​

С развитием языков с продвинутой системой типов (Rust, TypeScript, Scala 3, Haskell, OCaml) структуры данных стали нести больше статической информации:

  • Обобщённое программирование с ограничениями (bounds) — позволяет писать структуры, которые работают только с типами, реализующими определённые операции (например, Ord для сортировки, Hash + Eq для хеш-таблиц).
  • Зависимые типы и refinement types (в исследовательских языках, а также частично в F*, Liquid Haskell) — позволяют кодировать инварианты прямо в типе. Например, тип «непустой список» или «дерево поиска с ключами в диапазоне [a, b]». Компилятор проверяет соблюдение таких условий на этапе сборки.
  • Алгебраические типы данных (ADT) — суммы (Either, Option) и произведения (кортежи, записи) позволяют точно моделировать структуры с вариантами: дерево как Leaf | Node(left, value, right), очередь как Empty | Cons(head, tail). Это исключает ошибки вроде обращения к пустой очереди на уровне типов.

Особняком стоит Rust, где система владения (ownership) и заимствования (borrowing) позволяет реализовывать сложные структуры (например, графы с циклами, неизменяемые и изменяемые ссылки одновременно) без сборщика мусора и без гонок данных — проверка выполняется на этапе компиляции. Например, Rc<RefCell<T>> и Arc<Mutex<T>> — это гарантированные способы совместного владения: первый — для однопоточного случая, второй — для многопоточного.

6.4. Специализированные структуры для новых доменов​

По мере появления новых классов задач возникают и новые структуры, оптимизированные под конкретные паттерны доступа:

  • Графы:

    • CSR (Compressed Sparse Row) — компактное представление разреженных графов (и матриц), позволяющее быстро перебирать соседей вершины, при минимальном расходе памяти.
    • GraphBLAS — стандарт интерфейса для операций над графами в виде линейной алгебры (матричные операции над булевыми/полукольцевыми структурами), что открывает путь к аппаратному ускорению на GPU и FPGA.

  • Пространственные данные:

    • R‑деревья и их варианты (R*‑деревья, PH‑деревья) — для индексации прямоугольников, геометрических объектов, временных интервалов.
    • QuadTree / Octree — рекурсивное разбиение пространства, эффективно для динамических сцен (игры, симуляции).
    • Z‑order curve и Hilbert curve — методы линеаризации многомерных данных для эффективного хранения в B‑деревьях (используются в ClickHouse, DuckDB).

  • Временные ряды:

    • Delta-кодирование и GORILLA-компрессия (Facebook, 2015) — кодирование разностей времён и значений с использованием переменной длины и XOR, что позволяет хранить миллионы точек на один сервер.
    • TimescaleDB chunks — разбиение по времени на физические сегменты, которые управляются независимо (архивирование, сжатие, параллельный запрос).

  • Потоковые данные:

    • Коллективные структуры (sketches): HyperLogLog (оценка мощности множества), Count-Min Sketch (оценка частот), Bloom Filter (проверка принадлежности с ложноположительными срабатываниями). Все они используют вероятностные алгоритмы для работы с объёмами, превышающими RAM, с гарантированной ошибкой.
6.5. Автоматизация проектирования и синтез​

Появление инструментов формальной верификации (например, Dafny, F*, TLA⁺) и синтеза программ позволяет доказывать корректность структуры данных автоматически. Например, в Dafny можно определить инвариант AVL‑дерева, а компилятор проверит, что все операции его сохраняют.

Также развиваются системы, которые предлагают структуру данных на основе спецификации операций: если указано, что нужны insert, delete, range_query, система может предложить B⁺‑дерево; если — push, pop, peek — стек на массиве; если — merge, split, find-min — пара левых куч или фибоначчиева куча.